H: Animasembler sa vracia
35 bodov	Časový limit: 2000 ms

Po tom, ako sa s vašou pomocou zvieratká na školskom kole zoznámili s jazykom Animasembler, začalo ich baviť v tomto jazyku vytvárať svoje vlastné užitočné aj neužitočné programy. Pri ich vytváraní sa im ale často stáva, že nejaký program beží dlho, predlho, ešte dlhšie a stále nekončí. Skončí tento program vôbec niekedy?

Neskôr v zadaní nájdete špecifikáciu jazyka Animasembler. Tento text je rovnaký ako v zadaniach školského kola. Ak ste sa s ním počas školského kola oboznámili, zrejme ho nepotrebujete čítať znova.

Úloha, vstup a výstup

Na vstupe máte korektný program v jazyku Animasembler. Tento program pozostáva z najviac 100 riadkov, každý z týchto riadkov obsahuje najviac 100 znakov. Môžete predpokladať, že tento program deklaruje najviac jednu premennú. Môžete tiež predpokladať, že tento program načítava zo vstupu najviac jedno číslo. Presnejšie, nemôže sa stač nič takého:

.program NiekedyDvaVstupy
.data a
.kod
nacitaj a
skocaknula a 17
nacitaj a

Program v príklade načítava prvé číslo. Ak je toto číslo nula, potom skočí ďaleko za koniec programu, čím sa jeho vykonávanie ukončí. V opačnom prípade načítava zo vstupu druhé číslo. Môžete predpokladať, že programy na vstupe takto postavené nebudú.

Na výstup vypíšte, pre ktoré vstupné hodnoty program na vstupe zastane a pre ktoré nie. Ak je pre interval vstupných hodnôt odpoveď rovnaká, vypíšte tieto hodnoty ako interval. Intervaly vypíšte v poradí podľa rastúceho začiatku. Všetky intervaly na výstupe musia mať prázdny prienik, musí ich byť najmenší možný počet a dokopy musia tvoriť celý rozsah 0 až 65,535. Presný formát si pozrite v príkladoch.

Ak program hodnotu na vstupe neprečíta, jeho správanie od nej nezávisí. Vtedy je teda na výstupe len jeden riadok s intervalom všetkých vstupných hodnôt. V tejto úlohe je pamäťový limit 256 MB. Riešenia v Pythone možno na niektorých vstupoch nepobehajú.

Popis jazyka Animasembler

Na každom riadku je direktíva, inštrukcia alebo komentár. Žiaden riadok nesmie byť prázdny. Program pracuje len s celými číslami v rozsahu 0 až 65,535 (nemá žiadne znaky, stringy, polia ani iné typy). Program môže načítavať čísla zo vstupu a vypisovať ich na výstup. Jazyk je citlivý na nadbytočný whitespace. Okrem medzier, ktoré sú explicitne spomenuté v tejto špecifikácii sa v programe nesmú vyskytovať žiadne iné medzery. Program je case-sensitive: MenoPremennej a menoPremennej sú dve rôzne premenné.

Direktíva je riadok začínajúci bodkou. Každý program začína povinnou direktívou .program, za ktorou nasleduje jedna medzera a neprázdny reťazec – meno programu. Tento reťazec pozostáva z malých a veľkých písmen anglickej abecedy a jeho dĺžka nepresahuje 50.

Za prvým riadkom môže nasledovať 0 až neobmedzene veľa direktív .data, ktoré definujú premenné. Každý riadok s direktívou .data definuje jednu. Za direktívou .data nasleduje jedna medzera a meno premennej: neprázdny reťazec malých a veľkých písmen anglickej abecedy, ktorého dĺžka nepresahuje 50. Na začiatku behu programu má každá premenná hodnotu 0. Jedna premenná môže byť definovaná aj na viacerých riadkoch. Premenná môže mať rovnaký názov ako program. Nie je chybou, ak definujeme premennú a v programe ju nepoužijeme.

Za týmito riadkami nasleduje povinná direktíva .kod, ktorá označuje počiatočné miesto vykonávania programu. Táto direktíva nemá žiadne parametre, takže hneď sa znakom d nasleduje znak nového riadku. Jazyk nemá žiadne iné direktívy.

Za direktívou .kod nasleduje 0 až neobmedzene veľa inštrukcií – na každom riadku jedna. Inštrukcie jazyka sú popísané v nasledujúcej tabuľke spolu s definíciou ich prípadných parametrov. Keď sa spomína premenná, myslí sa tým premenná definovaná na začiatku programu direktívou .data. Žiadne iné premenné v jazyku nie sú. Všetky číselné rozsahy obsahujú aj obe okrajové hodnoty.

Formát inštrukcie	Parameter 1	Parameter 2
scitaj par1 par2	Celé číslo od 0 po 65,535 alebo premenná	Premenná
odcitaj par1 par2	Celé číslo od 0 po 65,535 alebo premenná	Premenná
vynasob par1 par2	Celé číslo od 0 po 65,535 alebo premenná	Premenná
vydel par2 par2	Celé číslo od 0 po 65,535 alebo premenná	Premenná
prirad par1 par2	Celé číslo od 0 po 65,535 alebo premenná	Premenná
skocaknula par1 par2	Celé číslo od 0 po 65,535 alebo premenná	Celé číslo od -65,535 po 65,535
skocaknenula par1 par2	Celé číslo od 0 po 65,535 alebo premenná	Celé číslo od -65,535 po 65,535
nacitaj par1	Premenná	-
vypis par1	Celé číslo od 0 po 65,535 alebo premenná	-
skonci	-	-

Každý riadok s inštrukciou začína menom inštrukcie. Ak inštrukcia nemá parameter (napríklad skonci), potom hneď za jej menom nasleduje znak nového riadku. V prípade, že má inštrukcia parameter alebo parametre, sú tieto navzájom od názvu inštrukcie a od seba navzájom oddelené práve jednou medzerou. Každá inštrukcia sa môže vyskytnúť len s počtom parametrov podľa špecifikácie vyššie a tieto parametre musia spĺňať obmedzenia definované v tejto špecifikácii.

Pri vykonávaní aritmetických inštrukcií sa najprv načítajú hodnoty z premenných, potom sa vyhodnotí výsledok a až potom sa výsledok zapisuje. Je teda úplne v poriadku zavolať:

scitaj a a

Táto inštrukcia si interne vypočíta 2*a a potom túto hodnotu zapíše do premennej a. Jazyk pripúšťa len skutočné celočíselné konštanty a premenné. Nesmie sa použiť výraz. Nemôžeme teda napísať prirad 3+5 a ani scitaj a*3 b.

Hociktorý riadok v programe okrem prvého môže byt komentár. Takýto riadok začína znakom #, po ktorom môže nasledovať ľubovoľný reťazec písmen, medzier, čísiel, bodiek, znaku mínus a mriežok, ktorého dĺžka nepresahuje 100. Okrem obmedzenia dĺžky na tento reťazec nie sú kladené žiadne požiadavky.

Prvou inštrukciou, ktorá sa vykoná, je inštrukcia nasledujúca za direktívou .kod. Potom sa vykonávajú inštrukcie jedna za druhou s výnimkou inštrukcií skoku. Pri počítaní cieľového riadku skoku sa neberú do úvahy riadky s komentárom. Skok mimo program alebo na riadok s direktívou znamená ukončenie programu. Program končí aj vtedy, ak by sa mala vykonať inštrukcia nasledujúca za poslednou.

Príklad programu v Animasembleri

Uveďme si ako príklad program Mocnina:

.program Mocnina
.data n
.data vysledok
.kod
nacitaj n
prirad 1 vysledok
# v n mame zapamatane kolkokrat este musime vynasobit vysledok hodnotou 2.
skocaknula n 4
vynasob 2 vysledok
odcitaj 1 n
# skocaknula 0 je priklad nepodmieneneho skoku.
skocaknula 0 -3
vypis vysledok
skonci

Tento program definuje dve premenné. Jednu hodnotu načíta zo vstupu, do druhej sa na úvod priradí 1. Potom sa opakuje cyklus, pri ktorom sa vynásobí premenná vysledok dvomi a odčíta od n jedna. Keď je hodnota n nula, program vypíše výsledok a skončí. Ak si hodnotu v premennej n interpretujeme ako počet, koľkokrát sa má ešte zopakovať cyklus, potom pomerne ľahko vidno, že náš program počíta n-tú mocninu čísla 2.

Poznamenajme, že v prípade, že sa na vstupe nachádza napríklad číslo n = 25, potom náš program skončí skôr, ako príde k výpisu: hodnota v premennej vysledok by totiž v istom momente behu bola príliš veľká.

Príklady

V papierovom zadaní máte možno nesprávny tretí príklad. V tomto zadaní a na testovači je opravený. Zmenil sa len vstup. Výstup zostal rovnaký.

Input:

.program VzdyZastane
.data x
.kod
scitaj 1 x

Output:

0-65535 ZASTANE

Tento program sa na vstup nepozerá. Preto zastane bez ohľadu na to, aká hodnota tam je.

Input:

.program NiekedyZastane
.data a
.kod
nacitaj a
skocaknula a 95
odcitaj 1 a
skocaknenula a 2
skocaknula a 0

Output:

0 ZASTANE
1 NEZASTANE
2-65535 ZASTANE

Ak je na vstupe 1, potom sa program dostane až na poslednú inštrukciu. V opačnom prípade počas behu odskočí na príliš vzdialený riadok, čo znamená koniec jeho vykonávania.

Input:

.program NiekedyZastane
.data a
.kod
nacitaj a
odcitaj 4 a
skocaknula a 0
vydel 5 a
skocaknula a 7
skocaknenula a 0

Output:

0-3 ZASTANE
4 NEZASTANE
5-8 ZASTANE
9-65535 NEZASTANE

---